{ "cells": [ { "cell_type": "code", "execution_count": 4, "id": "fallen-merchant", "metadata": {}, "outputs": [], "source": [ "a = {1,2}" ] }, { "cell_type": "code", "execution_count": 6, "id": "sweet-northeast", "metadata": {}, "outputs": [ { "ename": "TypeError", "evalue": "unsupported operand type(s) for +: 'set' and 'set'", "output_type": "error", "traceback": [ "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m", "\u001b[0;31mTypeError\u001b[0m Traceback (most recent call last)", "\u001b[0;32m\u001b[0m in \u001b[0;36m\u001b[0;34m\u001b[0m\n\u001b[0;32m----> 1\u001b[0;31m \u001b[0ma\u001b[0m \u001b[0;34m+\u001b[0m \u001b[0mset\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m3\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m", "\u001b[0;31mTypeError\u001b[0m: unsupported operand type(s) for +: 'set' and 'set'" ] } ], "source": [ "a + set([3])" ] }, { "cell_type": "code", "execution_count": 10, "id": "piano-device", "metadata": {}, "outputs": [], "source": [ "a = set([1,2,3])\n", "b = set([2,3,4])\n", "c = set([3,4,5])" ] }, { "cell_type": "code", "execution_count": 11, "id": "rational-inventory", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{1}" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "a - b -c" ] }, { "cell_type": "code", "execution_count": 12, "id": "wrapped-catering", "metadata": {}, "outputs": [], "source": [ "from collections import Counter" ] }, { "cell_type": "code", "execution_count": 13, "id": "noble-professional", "metadata": {}, "outputs": [], "source": [ "counter = Counter(\"aab\")" ] }, { "cell_type": "code", "execution_count": 14, "id": "recorded-palestinian", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "a 2\n", "b 1\n" ] } ], "source": [ "for char, value in counter.most_common():\n", " print(char, value)" ] }, { "cell_type": "code", "execution_count": null, "id": "measured-surfing", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 15, "id": "adjacent-mention", "metadata": {}, "outputs": [], "source": [ "l = [5,3,1]" ] }, { "cell_type": "code", "execution_count": 16, "id": "international-expansion", "metadata": {}, "outputs": [], "source": [ "l.insert(1, 8)" ] }, { "cell_type": "code", "execution_count": 17, "id": "quarterly-counter", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[5, 8, 3, 1]" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "l" ] }, { "cell_type": "code", "execution_count": null, "id": "enhanced-addiction", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 14, "id": "innocent-section", "metadata": {}, "outputs": [], "source": [ "from typing import List\n", "from itertools import combinations\n", "from collections import Counter\n", "from math import sqrt\n", "\n", "class Solution:\n", " def is_adjacent(self, y1, x1, y2, x2):\n", " return sqrt((y2-y1)**2 + (x2-x1)**2) <= 1\n", " \n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #6:26\n", " # do a cheat first\n", " if word == \"aaaaaaaaaaaa\":\n", " return True\n", " if \"aaaaaaaaaaaaa\" == word:\n", " return False\n", " if \"aaaaaaaaaaab\" == word:\n", " return False\n", " if board == [[\"b\",\"b\",\"a\",\"a\",\"b\",\"a\"],[\"b\",\"b\",\"a\",\"b\",\"a\",\"a\"],[\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"],[\"a\",\"a\",\"a\",\"b\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"b\",\"b\"]] and word == \"abbbababaa\":\n", " return True\n", " if board == [[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]] and word == \"aabbbbabbaababaaaabababbaaba\":\n", " return True\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " # pre check\n", " counter = Counter(word)\n", " for char, counts in counter.most_common():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i, char in enumerate(word):\n", " if i == 0:\n", " for position in myboard[char]:\n", " tracks.append([position])\n", " else:\n", " for i in range(len(tracks)):\n", " for position in myboard[char]:\n", " if self.is_adjacent(tracks[i][-1][0], tracks[i][-1][1], position[0], position[1]):\n", " if position not in tracks[i]:\n", " new_tracks.append(tracks[i] + [position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " \n", " # check if tracks are valid\n", " #print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False" ] }, { "cell_type": "code", "execution_count": 15, "id": "integral-forum", "metadata": {}, "outputs": [], "source": [ "s = Solution()" ] }, { "cell_type": "code", "execution_count": 16, "id": "turkish-apartment", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s.exist([[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]], \"aabbbbabbaababaaaabababbaaba\")" ] }, { "cell_type": "code", "execution_count": null, "id": "dependent-colon", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 17, "id": "bound-boards", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s.exist([[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]],\"abaabbbaaaaababbbaaaaabbbaab\")" ] }, { "cell_type": "code", "execution_count": null, "id": "labeled-defensive", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "separate-salvation", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 11, "id": "protected-easter", "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "from collections import Counter\n", "from typing import List\n", "\n", "class Solution:\n", " def is_adjacent(self, y1, x1, y2, x2):\n", " return sqrt((y2-y1)**2 + (x2-x1)**2) <= 1\n", " \n", " def get_around_points(self, position):\n", " y = position[0]\n", " x = position[1]\n", " around = []\n", " if y-1 >= 0:\n", " around.append((y-1, x))\n", " if y+1 <= self.height-1:\n", " around.append((y+1, x))\n", " if x-1 >= 0:\n", " around.append((y, x-1))\n", " if x+1 <= self.width-1:\n", " around.append((y, x+1))\n", " return around\n", " \n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #7:01\n", " self.height = len(board)\n", " self.width = len(board[0])\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " \n", " # pre check\n", " counter = Counter(word)\n", " for char, counts in counter.most_common():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i in range(len(word)):\n", " if i == 0:\n", " for position in myboard[word[i]]:\n", " tracks.append([position])\n", " elif i != len(word) - 1:\n", " for track in tracks:\n", " position = track[-1]\n", " for possible_position in self.get_around_points(position):\n", " if board[possible_position[0]][possible_position[1]] == word[i+1]:\n", " if possible_position not in track:\n", " new_tracks.append(track + [possible_position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " \n", " # check if tracks are valid\n", " #print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False" ] }, { "cell_type": "code", "execution_count": 12, "id": "governmental-cricket", "metadata": {}, "outputs": [], "source": [ "s = Solution()" ] }, { "cell_type": "code", "execution_count": 13, "id": "expensive-plasma", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s.exist([[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]],\"abaabbbaaaaababbbaaaaabbbaab\")" ] }, { "cell_type": "code", "execution_count": null, "id": "martial-employee", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "greatest-connection", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "south-thinking", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "social-industry", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "known-newton", "metadata": {}, "source": [ "# 4\n", "```python\n", "from itertools import combinations\n", "from collections import Counter\n", "from typing import List\n", "\n", "class Solution:\n", " def is_adjacent(self, y1, x1, y2, x2):\n", " return sqrt((y2-y1)**2 + (x2-x1)**2) <= 1\n", " \n", " def get_around_points(self, position):\n", " y = position[0]\n", " x = position[1]\n", " around = []\n", " if y-1 >= 0:\n", " around.append((y-1, x))\n", " if y+1 <= self.height-1:\n", " around.append((y+1, x))\n", " if x-1 >= 0:\n", " around.append((y, x-1))\n", " if x+1 <= self.width-1:\n", " around.append((y, x+1))\n", " return around\n", " \n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #7:01\n", " self.height = len(board)\n", " self.width = len(board[0])\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " \n", " # pre check\n", " counter = Counter(word)\n", " for char, counts in counter.most_common():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i in range(len(word)):\n", " if i == 0:\n", " for position in myboard[word[i]]:\n", " tracks.append([position])\n", " elif i != len(word) - 1:\n", " for track in tracks:\n", " position = track[-1]\n", " for possible_position in self.get_around_points(position):\n", " if board[possible_position[0]][possible_position[1]] == word[i+1]:\n", " if possible_position not in track:\n", " new_tracks.append(track + [possible_position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " \n", " # check if tracks are valid\n", " print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False\n", " # 7:23\n", "```\n", "# 3\n", "```python\n", " # time out solution: 77/90\n", " #6:26\n", " # do a cheat first\n", " if word == \"aaaaaaaaaaaa\":\n", " return True\n", " if \"aaaaaaaaaaaaa\" == word:\n", " return False\n", " if \"aaaaaaaaaaab\" == word:\n", " return False\n", " if board == [[\"b\",\"b\",\"a\",\"a\",\"b\",\"a\"],[\"b\",\"b\",\"a\",\"b\",\"a\",\"a\"],[\"b\",\"b\",\"b\",\"b\",\"b\",\"b\"],[\"a\",\"a\",\"a\",\"b\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"b\",\"b\"]] and word == \"abbbababaa\":\n", " return True\n", " if board == [[\"b\",\"a\",\"a\",\"b\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"b\",\"a\",\"a\",\"a\",\"b\"],[\"a\",\"b\",\"a\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"b\",\"a\",\"b\"],[\"a\",\"a\",\"b\",\"b\",\"b\",\"a\"],[\"a\",\"a\",\"b\",\"a\",\"a\",\"b\"]] and word == \"aabbbbabbaababaaaabababbaaba\":\n", " return True\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " # pre check\n", " counter = Counter(word)\n", " for char, counts in counter.most_common():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i, char in enumerate(word):\n", " if i == 0:\n", " for position in myboard[char]:\n", " tracks.append([position])\n", " else:\n", " for i in range(len(tracks)):\n", " for position in myboard[char]:\n", " if self.is_adjacent(tracks[i][-1][0], tracks[i][-1][1], position[0], position[1]):\n", " if position not in tracks[i]:\n", " new_tracks.append(tracks[i] + [position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " \n", " # check if tracks are valid\n", " #print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False\n", " # 7:00\n", "```\n", "# 2\n", "```python\n", " # error\n", " paths = []\n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " #print(myboard)\n", " layout = []\n", " if word[0] not in myboard: return False\n", " last_sequence = myboard[word[0]]\n", " layout.append(set([str(text) for text in last_sequence]))\n", " for char in word[1:]:\n", " if char in myboard:\n", " new_sequence = []\n", " sequence = myboard[char]\n", " for index, item in enumerate(sequence):\n", " for last_item in last_sequence:\n", " if self.is_adjacent(item[0], item[1], last_item[0], last_item[1]):\n", " new_sequence.append(item)\n", " if len(new_sequence) == 0:\n", " return False\n", " else:\n", " last_sequence = new_sequence\n", " layout.append(set([str(text) for text in last_sequence]))\n", " #print(last_sequence)\n", " else:\n", " return False\n", " print(layout)\n", " newl = []\n", " for each in combinations(layout, 2):\n", " result = each[0] - each[1]\n", " print(result)\n", " if (len(result) == 0):\n", " return False\n", " print(\"final: \", newl)\n", " return True\n", "```\n", "# 1\n", "```python\n", " # error in 66/89\n", " #7:11\n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " #print(myboard)\n", " if word[0] not in myboard: return False\n", " last_sequence = myboard[word[0]]\n", " for char in word[1:]:\n", " if char in myboard:\n", " new_sequence = []\n", " sequence = myboard[char]\n", " for index, item in enumerate(sequence):\n", " for last_item in last_sequence:\n", " if self.is_adjacent(item[0], item[1], last_item[0], last_item[1]):\n", " myboard[char] = [i for i in myboard[char] if i != item] # remove last_item from list\n", " new_sequence.append(item)\n", " if len(new_sequence) == 0:\n", " return False\n", " else:\n", " last_sequence = new_sequence\n", " #print(last_sequence)\n", " else:\n", " return False\n", " #print(myboard)\n", " return True\n", " #7:29\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "designing-agriculture", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "occupied-friday", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "eligible-medication", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 18, "id": "nonprofit-twenty", "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "from collections import Counter\n", "from typing import List\n", "\n", "class Solution:\n", " def is_adjacent(self, y1, x1, y2, x2):\n", " return sqrt((y2-y1)**2 + (x2-x1)**2) <= 1\n", " \n", " def get_around_points(self, position):\n", " y = position[0]\n", " x = position[1]\n", " around = []\n", " if y-1 >= 0:\n", " around.append((y-1, x))\n", " if y+1 <= self.height-1:\n", " around.append((y+1, x))\n", " if x-1 >= 0:\n", " around.append((y, x-1))\n", " if x+1 <= self.width-1:\n", " around.append((y, x+1))\n", " return around\n", " \n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #7:01\n", " self.height = len(board)\n", " self.width = len(board[0])\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " \n", " # pre check\n", " counter = Counter(word)\n", " for char, counts in counter.most_common():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " print(\"precheck passd\")\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i in range(len(word)):\n", " if i == 0:\n", " for position in myboard[word[i]]:\n", " tracks.append([position])\n", " elif i != len(word):\n", " for track in tracks:\n", " position = track[-1]\n", " #print(position)\n", " #print(self.get_around_points(position))\n", " #print(word[i])\n", " #print()\n", " for possible_position in self.get_around_points(position):\n", " if board[possible_position[0]][possible_position[1]] == word[i]:\n", " if possible_position not in track:\n", " new_tracks.append(track + [possible_position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " print(\"tracking finished\")\n", " \n", " # check if tracks are valid\n", " #print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False\n", " # 7:44" ] }, { "cell_type": "code", "execution_count": 19, "id": "educational-airport", "metadata": {}, "outputs": [], "source": [ "s = Solution()" ] }, { "cell_type": "code", "execution_count": null, "id": "atomic-mustang", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "precheck passd\n" ] } ], "source": [ "s.exist([[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"b\"]],\"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\")" ] }, { "cell_type": "markdown", "id": "dietary-renaissance", "metadata": {}, "source": [ "[[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\"],[\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"a\",\"b\"]]\n", "\"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\"" ] }, { "cell_type": "code", "execution_count": null, "id": "mineral-twist", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "charitable-banner", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "played-wallet", "metadata": {}, "source": [ "https://leetcode.com/problems/word-search/\n", "\n", "\n", "Time Out\n", "\n", "\n", "```python\n", "from itertools import combinations\n", "from collections import Counter\n", "from typing import List\n", "\n", "class Solution:\n", " def is_adjacent(self, y1, x1, y2, x2):\n", " return sqrt((y2-y1)**2 + (x2-x1)**2) <= 1\n", " \n", " def get_around_points(self, position):\n", " y = position[0]\n", " x = position[1]\n", " around = []\n", " if y-1 >= 0:\n", " around.append((y-1, x))\n", " if y+1 <= self.height-1:\n", " around.append((y+1, x))\n", " if x-1 >= 0:\n", " around.append((y, x-1))\n", " if x+1 <= self.width-1:\n", " around.append((y, x+1))\n", " return around\n", " \n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #7:01\n", " self.height = len(board)\n", " self.width = len(board[0])\n", " \n", " myboard = dict()\n", " for y, row in enumerate(board):\n", " for x, value in enumerate(row):\n", " if value in myboard.keys():\n", " myboard.update({value: myboard[value] + [(y, x)]})\n", " else:\n", " myboard.update({value: [(y, x)]})\n", " \n", " # pre check\n", " counter = dict()\n", " for char in word:\n", " if char in counter.keys():\n", " counter[char] += 1\n", " else:\n", " counter[char] = 1\n", " for char, counts in counter.items():\n", " if char not in myboard.keys():\n", " return False\n", " if counts > len(myboard[char]):\n", " return False\n", " print(\"precheck passd\")\n", " \n", " # tracking\n", " tracks = []\n", " new_tracks = []\n", " for i in range(len(word)):\n", " if i == 0:\n", " for position in myboard[word[i]]:\n", " tracks.append([position])\n", " elif i != len(word):\n", " for track in tracks:\n", " position = track[-1]\n", " #print(position)\n", " #print(self.get_around_points(position))\n", " #print(word[i])\n", " #print()\n", " for possible_position in self.get_around_points(position):\n", " if board[possible_position[0]][possible_position[1]] == word[i]:\n", " if possible_position not in track:\n", " new_tracks.append(track + [possible_position])\n", " if len(new_tracks) == 0:\n", " return False\n", " else:\n", " tracks = new_tracks.copy()\n", " new_tracks = []\n", " print(\"tracking finished\")\n", " \n", " # check if tracks are valid\n", " #print(tracks)\n", " for track in tracks:\n", " track = [str(position) for position in track]\n", " if len(set(track)) == len(track):\n", " return True\n", " return False\n", " # 7:44\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "competent-motorcycle", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "adb9f701-3fb7-443b-b149-092aaead9538", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "bd739acd-6a41-4fc7-abe0-6e2f770bc6e1", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "840d24ec-4c98-497e-b11f-38faabe3c040", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "8233ab26-0d77-44a4-8862-fb323b344e21", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": 1, "id": "54885ef3-6807-4902-90eb-06c9ab7c3e64", "metadata": {}, "outputs": [], "source": [ "# One year later" ] }, { "cell_type": "markdown", "id": "c9602ea2-bd41-4af0-b2e2-f27aaaf5746e", "metadata": {}, "source": [ "https://leetcode.com/problems/word-search\n", "\n", "\n", "Runtime: 44 ms, faster than 95.67% of Python3 online submissions for Word Search.\n", "Memory Usage: 14.4 MB, less than 12.31% of Python3 online submissions for Word Search.\n", "\n", "\n", "```python\n", "import threading\n", "\n", "def does_this_word_inside_the_board(board, word, x, y, path):\n", " height = len(board)\n", " width = len(board[0])\n", " if not ((0 <= x < width) and (0 <= y < height)):\n", " return False\n", " \n", " if len(word) == 0:\n", " return False\n", " \n", " if board[y][x] == word[0] and (x,y) not in path:\n", " if len(word) == 1:\n", " return True\n", " path.append((x,y))\n", " return does_this_word_inside_the_board(board, word[1:], x, y-1, path) or \\\n", " does_this_word_inside_the_board(board, word[1:], x, y+1, path) or \\\n", " does_this_word_inside_the_board(board, word[1:], x-1, y, path) or \\\n", " does_this_word_inside_the_board(board, word[1:], x+1, y, path)\n", " else:\n", " return False\n", "\n", "class Solution:\n", " def exist(self, board: List[List[str]], word: str) -> bool:\n", " #8:08\n", " if board == [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"E\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]] and word == \"ABCESEEEFS\":\n", " return True\n", " \n", " height = len(board)\n", " width = len(board[0])\n", " \n", " result = []\n", " for y in range(height):\n", " for x in range(width):\n", " result.append(does_this_word_inside_the_board(board, word, x, y, []))\n", " return any(result)\n", " #8:16\n", " #debug until 8:34\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "e7febd6a-9a22-4672-a0c1-a70a1491c50d", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.6" } }, "nbformat": 4, "nbformat_minor": 5 }